(display "\n========================================\n")
; 2.1.1 有理数实例
; (define (add-rat x y)
;     (make-rat (+ (* (numer x) (denom y))
;                  (* (numer y) (denom x)))
;               (* (denom x) (denom y))))

; (define (sub-rat x y)
;     (make-rat (- (* (numer x) (denom y))
;                  (* (numer y) (denom x)))
;               (* (denom x) (denom y))))

; (define (mul-rat x y)
;     (make-rat (* (numer x) (numer y))
;               (* (denom x) (denom y))))

; (define (div-rat x y)
;     (make-rat (* (numer x) (denom y))
;               (* (numer y) (denom x))))

; (define (equal-rat? x y)
;     (make-rat (= (* (numer x) (denom y))
;                  (* (numer y) (denom x)))))

; (define (make-rat n d) (cons n d))

; (define (numer x) (car x))

; (define (denom x) (cdr x))

; (define (print-rat x)
;     (display (numer x))
;     (display "/")
;     (display (denom x)))

; (define one-half (make-rat 1 2))

; (print-rat one-half)
; (newline)

; (define one-third (make-rat 1 3))

; (print-rat one-third)
; (newline)

; (print-rat (add-rat one-half one-third))
; (newline)

; (print-rat (sub-rat one-half one-third))
; (newline)

; (print-rat (mul-rat one-half one-third))
; (newline)

; (print-rat (div-rat one-half one-third))
; (newline)
; (print-rat (make-rat 2 3))

; (define (gcd a b)
;     (let ((n (remainder a b)))
;         (if (= n 0)
;             b
;             (gcd b n))))
; ; (display (gcd 30 20))
; ; (newline)

; (define (make-rat n d)
;     (let ((g (gcd n d)))
;         (cons (/ n g) (/ d g))))

; (print-rat (make-rat 20 30))

; 2.1.4 区间计算
; (define (add-interval x y)
;     (make-interval (+ (lower-bound x) (lower-bound y))
;                    (+ (upper-bound x) (upper-bound y))))

; (define (mul-interval x y)
;     (let ((p1 (* (lower-bound x) (lower-bound y)))
;           (p2 (* (lower-bound x) (upper-bound y)))
;           (p3 (* (upper-bound x) (lower-bound y)))
;           (p4 (* (upper-bound x) (upper-bound y))))
;          (make-interval (min p1 p2 p3 p4)
;                         (max p1 p2 p3 p4))))

; (define (div-interval x y)
;     (mul-interval x
;                   (make-interval (/ 1 (lower-bound y))
;                                  (/ 1 (upper-bound y)))))

; (define (make-interval a b) (cons a b))
; (define (lower-bound z) (car z))
; (define (upper-bound z) (cdr z))

; (define v1 (make-interval 1 2))
; (define v2 (make-interval 3 4))
; (display (div-interval v1 v2))

; 2.2.1 序列的表示
; (define one-through-four (list 1 2 3 4))
; (display one-through-four)
; (newline)
; (display (car one-through-four))
; (newline)
; (display (cdr one-through-four))
; (newline)
; (display (cadr one-through-four))
; (newline)
; (display (caddr one-through-four))
; (newline)
; (display (cons 5 one-through-four))
; (newline)
; (display (cons one-through-four 5))
; (newline)

; (define (list-ref items n)
;     (if (= n 0)
;         (car items)
;         (list-ref (cdr items) (- n 1))))
; (define squares (list 0 1 4 9 16 25))
; (display (list-ref squares 4))
; (newline)

; (define (length items)
;     (if (null? items)
;         0
;         (+ 1 (length (cdr items)))))
; (define odds (list 1 3 5 7 9 11))
; (define (length items)
;     (define (iter items count)
;         (if (null? items)
;             count
;             (iter (cdr items) (+ count 1))))
;     (iter items 0))
; (display (length odds))

; (define (append list1 list2)
;     (if (null? list1)
;         list2
;         (cons (car list1) (append (cdr list1) list2))))

; (display (append odds squares))
; (newline)
; (display (append squares odds))
; (newline)

; (define (scale-list items factor)
;     (if (null? items)
;         ()
;         (cons (* (car items) factor)
;               (scale-list (cdr items) factor))))

; (display (scale-list odds 10))
; (newline)

; (define (map proc items)
;     (if (null? items)
;         ()
;         (cons (proc (car items))
;               (map proc (cdr items)))))

; (display (map (lambda (x) (* x x)) odds))
; (newline)

; (define (scale-list items factor)
;     (map (lambda (x) (* x factor)) items))
; (display (scale-list odds 2))

; 2.2.2 Hierarchical Structures
; (define (count-leaves x)
;     (cond ((null? x) 0)
;           ((not (pair? x)) 1)
;           (else (+ (count-leaves (car x))
;                    (count-leaves (cdr x))))))

; (define x (cons (list 1 2) (list 3 4)))
; (display (length x))
; (newline)
; (display (count-leaves x))
; (newline)
; (display (list x x))
; (newline)
; (display (length (list x x)))
; (newline)
; (display (count-leaves (list x x)))


; (define (scale-tree tree factor)
;     (cond ((null? tree) ())
;           ((not (pair? tree)) (* tree factor))
;           (else (cons (scale-tree (car tree) factor)
;                       (scale-tree (cdr tree) factor)))))
; (define tree (list 1 (list 2 (list 3 4) 5) (list 6 7)))
; (display tree)
; (newline)
; (display (scale-tree tree 2))
; (newline)

; (define (scale-tree tree factor)
;     (map (lambda (sub-tree)
;             (if (pair? sub-tree)
;                 (scale-tree sub-tree factor)
;                 (* sub-tree factor)))
;          tree))
; (display (scale-tree tree 2))
; (newline)


; 2.3 Symbolic Data
; (define (sum-odd-squares tree)
;     (cond ((null? tree) 0)
;           ((not (pair? tree))
;             (if (odd? tree)
;                 (square tree)
;                 0))
;           (else (+ (sum-odd-squares (car tree))
;                    (sum-odd-squares (cdr tree))))))
; (define tree (list 1 2 3 4 5 6 7))
; (display tree)
; (newline)
; (display (sum-odd-squares tree))
; (newline)

; (define (fib k)
;     (cond ((= k 0) 0)
;           ((= k 1) 1)
;           (else (+ (fib (- k 1))
;                    (fib (- k 2))))))

; (define (even-fib n)
;     (define (next k)
;         (if (> k n)
;             ()
;             (let ((f (fib k)))
;                 (if (even? f)
;                     (cons f (next (+ k 1)))
;                     (next (+ k 1))))))
;     (next 0))

; (display (even-fib 20))

; (display (map square (list 1 2 3 4 5)))
; (newline)

; (define (filter predicate sequence)
;     (cond ((null? sequence) ())
;           ((predicate (car sequence))
;             (cons (car sequence)
;                   (filter predicate (cdr sequence))))
;           (else (filter predicate (cdr sequence)))))

; (display (filter odd? (list 1 2 3 4 5)))
; (newline)

; (define (accumulate op initial sequence)
;     (if (null? sequence)
;         initial
;         (op (car sequence)
;             (accumulate op initial (cdr sequence)))))

; (display (accumulate + 0 (list 1 2 3 4 5)))
; (newline)

(define (enumerate-interval low high)
    (if (> low high)
        ()
        (cons low (enumerate-interval (+ low 1) high))))

; (display (enumerate-interval 0 3))
; (newline)

; (define (enumerate-tree tree)
;     (cond ((null? tree) ())
;           ((not (pair? tree)) (list tree))
;           (else (append (enumerate-tree (car tree))
;                         (enumerate-tree (cdr tree))))))

; (display (enumerate-tree (list 1 (list 2 3 (list 4 5) 6))))
; (newline)

; (define (sum-odd-squares tree)
;     (accumulate +
;                 0
;                 (map square
;                      (filter odd? (enumerate-tree tree)))))

; (display (sum-odd-squares tree))
; (newline)

; (define (even-fib n)
;     (accumulate cons
;                 ()
;                 (filter even?
;                         (map fib
;                              (enumerate-interval 0 n)))))

; (display (even-fib 6))
; (newline)

; (define (list-square-fib n)
;     (accumulate cons
;                 ()
;                 (map square
;                      (map fib (enumerate-interval 0 n)))))
; (display (list-square-fib 10))
; (newline)

; (define (product-of-square-of-odd-elements sequence)
;     (accumulate *
;                 1
;                 (filter odd?
;                         (map square sequence))))
; (display (product-of-square-of-odd-elements (list 1 2 3 4 5)))
; (newline)

; (define (salary-of-highest-paid-programmer records)
;     (accumulate max
;                 0
;                 (map salary
;                      (filter programmer? records))))

; (define (accumulate op initial sequence)
;     (if (null? sequence)
;         initial
;         (op (car sequence)
;             (accumulate op initial (cdr sequence)))))

; (define (flatmap proc seq)
;     (accumulate append () (map proc seq)))

; (define (prime-sum? pair)
;     (define (prime? n)
;         (define (iter i)
;             (cond ((> (* i i) n) #t)
;                   ((= (remainder n i) 0) #f)
;                   (else (iter (+ i 1)))))
;         (iter 2))
;     (prime? (+ (car pair) (cadr pair))))
; ; (display (prime-sum? (list 10 2)))
; ; (newline)

; (define (make-pair-sum pair)
;     (list (car pair) (cadr pair) (+ (car pair) (cadr pair))))
; ; (display (make-pair-sum (list 2 3)))
; ; (newline)

; (define (prime-sum-pair n)
;     (map make-pair-sum
;          (filter prime-sum?
;                  (flatmap (lambda (i)
;                                   (map (lambda (j) (list i j))
;                                        (enumerate-interval 1 (- i 1))))
;                           (enumerate-interval 1 n)))))
; ; (display (prime-sum-pair 6))
; ; (newline)

; (define (permutations s)
;     (define (remove item seq)
;         (filter (lambda (x) (not (= x item)))
;                 seq))
;     (if (null? s)
;         (list ())
;         (flatmap (lambda (x)
;                         (map (lambda (p) (cons x p))
;                             (permutations (remove x s))))
;                 s)))
; (display (permutations (list 1 2 3)))
; (newline)

; beside below flip-vert flip-horiz wave painter
; (define wave2 (beside wave (flip-vert wave)))
; (define wave4 (below wave2 wave2))

; (define (flipped-pairs painter)
;     (let ((painter2 (beside painter (flip-vert painter))))
;         (below painter2 painter2)))

; (define wave4 (flipped-pairs wave))

; (define (right-split painter n)
;     (if (= n 0)
;         painter
;         (let ((smaller (right-split painter (- n 1))))
;             (beside painter (below smaller smaller)))))

; (define (corner-split painter n)
;     (if (= n 0)
;         painter
;         (let ((up (up-split painter (- n 1)))
;               (right (right-split painter (- n 1))))
;             (let ((top-left (beside up up))
;                   (bottom-right (below right right))
;                   (corner (corner-split painter (- n 1)))))
;             (beside (below painter top-left)
;                     (below bottom-right corner)))))

; (define (square-limit painter n)
;     (let ((quarter (corner-split painter n)))
;         (let ((half (beside (flip-horiz quarter) quarter)))
;             (below (flip-vert half) half))))

; (define (square-of-four tl tr bl br)
;     (lambda (painter)
;             (let ((top (beside (tr painter) (tl painter)))
;                   (bottom (beside (br painter) (bl painter))))
;                 (below bottom top))))

; (define (flipped-pairs painter)
;     (let ((combine4 (square-of-four identity flip-vert
;                                    identity flip-vert)))
;         (combine4 painter)))

; (define (square-limit painter n)
;     (let ((combine4 (square-of-four flip-horiz identity
;                                     rotate180 flip-vert))) ; (flip-vert (flip-horiz painter))
;         (combine4 (corner-split painter n))))

; (define (frame-coord-map frame)
;     (lambda (v)
;             (add-vect
;                 (origin-frame frame)
;                 (add-vect (scale-vect (xcor-vect v)
;                                       (edge1-frame frame))
;                           (scale-vect (ycor-vect v)
;                                       (edge2-frame frame))))))

; (define (segment->painter segment-list)
;     (lambda (frame)
;         (for-each
;             (lambda (segment)
;                     (draw-line
;                         ((frame-coord-map frame) (start-segment segment))
;                         ((frame-coord-map frame) (end-segment segment))))
;             segment-list)))

; (define (transform-painter painter origin corner1 corner2)
;     (lambda (frame)
;         (let ((m (frame-coord-map frame)))
;             (let ((new-origin (m origin)))
;                 (painter
;                     (make-frame new-origin
;                                 (sub-vect (m corner1) new-origin)
;                                 (sub-vect (m corner2) new-origin)))))))

; (define (flip-vert painter)
;     (transform-painter painter
;                        (make-vect 0 1)
;                        (make-vect 1 1)
;                        (make-vect 0 0)))

; (define (shrink-to-upper-right painter)
;     (transform-painter painter
;                        (make-vect 0.5 0.5)
;                        (make-vect 1.0 0.5)
;                        (make-vect 0.5 1.0)))

; (define (rotate90 painter)
;     (transform-painter painter
;                        (make-vect 0 1)
;                        (make-vect 0 0)
;                        (make-vect 1 0)))

; (define (rotate270 painter)
;     (transform-painter painter
;                        (make-vect 1 0)
;                        (make-vect 1 1)
;                        (make-vect 0 0)))

; (define (squash-inwards painter)
;     (transform-painter painter
;                        (make-vect 0 0)
;                        (make-vect 0.65 0.35)
;                        (make-vect 0.35 0.65)))

; (define (beside painter1 painter2)
;     (let ((split-point (make-vect 0.5 0)))
;         (let ((paint-left
;                     (transform-painter painter1
;                                        (make-vect 0 0)
;                                        split-point
;                                        (make-vect 0 1)))))
;         (let ((paint-right
;                     (transform-painter painter2
;                                        split-point
;                                        (make-vect 1 0)
;                                        (make-vect 0.5 1)))))
;         (lambda (frame)
;             (paint-left frame)
;             (paint-right frame))))

; 2.3 Symbolic Data
; (define a 1)
; (define b 2)
; (display (list a b))
; (newline)
; (display (list 'a 'b))
; (newline)
; (display (list 'a b))
; (newline)
; (display (car '(a b c)))
; (newline)
; (display (cdr '(a b c)))
; (newline)

; (define (memq item x)
;     (cond ((null? x) false)
;           ((eq? item (car x)) x)
;           (else (memq item (cdr x)))))

; (define test1 (memq 'apple '(pear banana prune)))
; (display test1)
; (newline)

; (define test2 (memq 'apple '(prune apple pear banana)))
; (display test2)
; (newline)

; (define test3 (memq 'apple '(x (apple sauce) y apple pear)))
; (display test3)
; (newline)


; 2.3.2 Example: Symbolic Differentiation
; (define (variable? x) (symbol? x))

; (define (same-variable? v1 v2)
;     (and (variable? v1) (variable? v2) (eq? v1 v2)))

; (define (make-sum a1 a2) (list '+ a1 a2))

; (define (make-product m1 m2) (list '* m1 m2))

; (define (sum? x)
;     (and (pair? x) (eq? (car x) '+)))

; (define (addend s) (cadr s))

; (define (augend s) (caddr s))

; (define (product? x)
;     (and (pair? x) (eq? (car x) '*)))

; (define (multiplier p) (cadr p))

; (define (multiplicand p) (caddr p))

; (define (deriv exp var)
;     (cond   ((number? exp) 0)
;             ((variable? exp)
;                 (if (same-variable? exp var) 1 0))
;             ((sum? exp)
;                 (make-sum (deriv (addend exp) var)
;                           (deriv (augend exp) var)))
;             ((product? exp)
;                 (make-sum
;                     (make-product (multiplier exp)
;                                   (deriv (multiplicand exp) var))
;                     (make-product (deriv (multiplier exp) var)
;                                   (multiplicand exp))))
;             (else
;                 (error "Unknow exception type -- DERIV" exp))))

; (define (=number? exp num)
;     (and (number? exp) (= exp num)))

; (define (make-sum a1 a2)
;     (cond   ((=number? a1 0) a2)
;             ((=number? a2 0) a1)
;             ((and (number? a1) (number? a2)) (+ a1 a2))
;             (else (list '+ a1 a2))))

; (define (make-product m1 m2)
;     (cond   ((or (=number? m1 0) (=number? m2 0)) 0)
;             ((=number? m1 1) m2)
;             ((=number? m2 1) m1)
;             ((and (number? m1) (number? m2)) (* m1 m2))
;             (else (list '* m1 m2))))

; (display (deriv '(+ x 3) 'x))
; (newline)

; (display (deriv '(* x y) 'x))
; (newline)

; (display (deriv '(* (* x y) (+ x 3)) 'x))
; (newline)

; 2.3.3 Example: Representing Sets
; (define (element-of-set? x set)
;     (cond   ((null? set) #f)
;             ((equal? x (car set)) #t)
;             (else (element-of-set? x (cdr set)))))
; ; (display (element-of-set? 1 (list 1 2 3)))

; (define (adjoin-set x set)
;     (if (element-of-set? x set)
;         set
;         (cons x set)))
; ; (display (adjoin-set 0 (list 1 2 3)))

; (define (intersection-set set1 set2)
;     (cond   ((or (null? set1) (null? set2)) '())
;             ((element-of-set? (car set1) set2)
;                 (cons (car set1)
;                       (intersection-set (cdr set1) set2)))
;             (else (intersection-set (cdr set1) set2))))
; ; (display (intersection-set (list 1 2 3) (list 2 3 4)))


; (define (element-of-set? x set)
;     (cond   ((null? set) #f)
;             ((= x (car set)) #t)
;             ((< x (car set)) #f)
;             (else (element-of-set? x (cdr set)))))
; ; (display (element-of-set? 3 (list 1 2 3 4)))

; (define (intersection-set set1 set2)
;     (if (or (null? set1) (null? set2))
;         '()
;         (let ((x1 (car set1)) (x2 (car set2)))
;             (cond   ((= x1 x2)
;                         (cons x1
;                               (intersection-set (cdr set1) (cdr set2))))
;                     ((< x1 x2)
;                         (intersection-set (cdr set1) set2))
;                     (else
;                         (intersection-set set1 (cdr set2)))))))
; ; (display (intersection-set (list 1 2 3) (list 2 3 4)))

; (define (entry tree)
;         (car tree))
; ; (display (entry '()))

; (define (left-branch tree)
;         (cadr tree))
; ; (display (left-branch '()))

; (define (right-branch tree)
;         (caddr tree))
; ; (display (right-branch (list 1 2 3)))


; (define (make-tree entry left right)
;     (list entry left right))

; (define (element-of-set? x set)
;     (cond   ((null? set) #f)
;             ((= x (entry set)) #t)
;             ((< x (entry set))
;                 (element-of-set? x (left-branch set)))
;             ((> x (entry set))
;                 (element-of-set? x (right-branch set)))))

; (define tree (list 3 (list 2 '() '()) (list 4 '() '())))
; (display tree)

; (define (adjoin-set x set)
;     (cond   ((null? set) (make-tree x '() '()))
;             ((= x (entry set)) set)
;             ((< x (entry set))
;                 (make-tree (entry set)
;                            (adjoin-set x (left-branch set))
;                            (right-branch set)))
;             ((> x (entry set))
;                 (make-tree (entry set)
;                            (left-branch set)
;                            (adjoin-set x (right-branch set))))))

; (display (adjoin-set 3 tree))

(define (make-leaf symbol weight)
    (list 'leaf symbol weight))

(define (leaf? object)
    (eq? (car object) 'leaf))

(define (symbol-leaf x)
    (cadr x))

(define (weight-leaf x)
    (caddr x))

(define (left-branch tree)
    (car tree))

(define (right-branch tree)
    (cadr tree))

(define (symbols tree)
    (if (leaf? tree)
        (list (symbol-leaf tree))
        (caddr tree)))

(define (weight tree)
    (if (leaf? tree)
        (weight-leaf tree)
        (cadddr tree)))

(define (make-code-tree left right)
    (list left
          right
          (append (symbols left) (symbols right))
          (+ (weight left) (weight right))))

(define (decode bits tree)
    (define (iter bits current-branch)
        (if (null? bits)
            '()
            (let ((next-branch
                    (choose-branch (car bits) current-branch)))
                (if (leaf? next-branch)
                    (cons (symbol-leaf next-branch)
                          (iter (cdr bits) tree))
                    (iter (cdr bits) next-branch)))))
    (iter bits tree))

(define (choose-branch bit branch)
    (cond   ((= bit 0) (left-branch branch))
            ((= bit 1) (right-branch branch))
            (else (error "bad bit -- CHOOSE-BRANCH" bit))))

(define (adjoin-set x set)
    (cond   ((null? set) (list x))
            ((< (weight x) (weight (car set)))
                (cons x set))
            (else (cons (car set)
                        (adjoin-set x (cdr set))))))

(define (make-leaf-set pairs)
    (if (null? pairs)
        '()
        (let ((pair (car pairs)))
            (adjoin-set (make-leaf (car pair)
                                   (cadr pair))
                        (make-leaf-set (cdr pairs))))))
(display (make-leaf-set '((A 4) (B 2) (C 1) (D 1))))
(display "\n========================================\n")
